package com.scy.java.conllection;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;

/**
 * ArrayList:
 * 。基于数组，需要连续内存，随机访问快 (可以根据下标访问)尾部插入和删除
 * 性能可以，头部和中间插入删除慢 (数组扩容的问题因为次数不多影响不大所以不考虑)
 * 。可以CPU缓存，利用局部性原理。
 * ArrayList查询速度快，是因为连续的内存，比如：集合中的元素1的地址是0，
 * 里面都是整数，一个整数占4个字节，如果我们要查询的信息为5，那么5的索引为4
 * 其地址为：4*5+0=20
 *
 *
 * LinkedList:
 * 。基于双向链表，不需要连续内存，随机访问慢 (需要迭代遍历)头尾插入删除性
 * 能高，中间插入删除性能慢
 * 占内存很多
 */

//ArrayList、LinkedList查询性能的差距

/**
 * ArrayList查找数据花费时间为：11毫秒
 * linkedList查找数据花费时间为：46574毫秒
 * linkedList查询指定元素花费时间为：3599毫秒
 * ArrayList查找数据花费时间为：5毫秒
 */
public class RandomAccess {
    private final static int COUNT = 100000;
    public static void main(String[] args) {
        //创建ArrayList集合
        ArrayList<Integer> arrayList = new ArrayList<>();
        //创建LinkedList集合
        LinkedList<Integer> linkedList = new LinkedList<>();
        //动态为集合添加数据
        for(int i = 0; i < COUNT; i++) {
            arrayList.add(i);
            linkedList.add(i);
        }
        //ArrayList的随机访问性查询速度
        arrayListAccess(arrayList);//ArrayList查找数据花费时间为：11毫秒
        //LinkedList的随机访问性查询速度
        linkedListAccess(linkedList);//linkedList查找数据花费时间为：46574毫秒
        //查询指定元素，来测试两者的性能
        //LinkedList查询指定元素，测试速度
        linkedListAccess(10000,linkedList);//linkedList查询指定元素花费时间为：3599毫秒
        //ArrayList查询指定元素，测试速度
        arrayListAccess(10000,arrayList);//ArrayList查找数据花费时间为：5毫秒

    }

    //ArrayList查询指定元素，测试速度
    private static void arrayListAccess(
            int num, ArrayList<Integer> arrayList) {
        long begin = System.currentTimeMillis();
        //arrayList.size()集合的长度
        for (int i = 0; i < arrayList.size(); i++) {
            if (arrayList.get(i) == num){
                System.out.println(num);
            }
        }
        long end = System.currentTimeMillis();
        System.out.println("ArrayList查找数据花费时间为："+(end-begin)+"毫秒");

    }

    //测试LinkedList查询指定元素，测试速度
    private static void linkedListAccess(
            int num, LinkedList<Integer> linkedList) {
        long begin = System.currentTimeMillis();
        //linkedList.size()集合的长度
        for (int i = 0; i < linkedList.size(); i++) {
            if (linkedList.get(i) == num){
                System.out.println(num);
            }
        }
        long end = System.currentTimeMillis();
        System.out.println("linkedList查询指定元素花费时间为："+(end-begin)+"毫秒");

    }

    //测试LinkedList的随机访问性查询速度
    private static void linkedListAccess(LinkedList<Integer> linkedList) {
        long begin = System.currentTimeMillis();
        //linkedList.size()集合的长度
        for (int i = 0; i < linkedList.size(); i++) {
            //集合中的数据是有顺序的所以我们可以用二分查找法
            int index = Collections.binarySearch(
                    linkedList, linkedList.get(i));
            if (index != i){
                System.out.println("ERROR");
            }
        }
        long end = System.currentTimeMillis();
        System.out.println("linkedList查找数据花费时间为："+(end-begin)+"毫秒");

    }

    //测试ArrayList的随机访问性查询速度
    private static void arrayListAccess(ArrayList<Integer> arrayList) {
        long begin = System.currentTimeMillis();
        //arrayList.size()集合的长度
        for (int i = 0; i < arrayList.size(); i++) {
            //集合中的数据是有顺序的所以我们可以用二分查找法
            int index = Collections.binarySearch(
                    arrayList, arrayList.get(i));
            if (index != i){
                System.out.println("ERROR");
            }
        }
        long end = System.currentTimeMillis();
        System.out.println("ArrayList查找数据花费时间为："+(end-begin)+"毫秒");
    }
}
